Dense deployment of base stations or wireless access nodes may be used to address the exponential growth in wireless data traffic. The feasibility of a dense deployment of wireless access nodes is predicated on the existence of a backhaul network that can provide high data rate transport for each individual access node in the network. From the point of view of maximizing capacity, optical fiber based backhaul solutions are desirable and are suitable for new constructions. However, in existing buildings and infrastructure, the cost of installing new fibers to every access node in a very dense network can be prohibitive.
An alternative to the optical backhaul solution is the wireless self-backhaul solution, where the same access spectrum is used to provide transport. With self-backhauling, an access node serves not only its own assigned User Equipment (UE) in its vicinity but also its neighboring access nodes as a relaying node in order to route data towards and/or from an information aggregation node in the network. A group of self-backhauling access nodes can form a multi-hop mesh network. Access nodes cooperatively route each other's traffic to and from the aggregation node.
Finding an optimal (or close to optimal) route from a source node to a destination node in a multi-hop network often is formulated in terms of finding a route that maximizes or minimizes the value of a single route metric. The route metric may be, for example, route bit rate capacity, route power consumption, route latency, etc. If the route metric is simple enough—that is, if it is both monotonic and isotonic—there exist efficient polynomial-time algorithms for finding the optimal route, e.g., the Bellman-Ford algorithm and the Dijkstra algorithm. In the general case, however, the problem is Non-Deterministic Polynomial-Time hard (NP-hard), i.e., the computational complexity grows exponentially with the number of nodes.
Unfortunately, in practice, the desire to take multiple route properties into account in the route metric (e.g., both route bit rate and route latency) makes it difficult to formulate an appropriate route metric that is simple enough (i.e., is both monotonic and isotonic) to be used with existing polynomial-time algorithms (e.g., the Bellman-Ford algorithm and the Dijkstra algorithm) for finding the optimal route through a multi-hop wireless network. As such, finding optimal routes for a route metric that takes multiple route properties into account may be computationally unfeasible using known algorithms. As such, there is a need for systems and methods for finding an optimal, or close to optimal, route from a source node to a destination node in a multi-hop network when taking multiple route properties into consideration.